\chapter{Podstawowe pojęcia}\label{podstawowePojecia}

W tym rozdziale przedstawimy podstawowe pojęcia, fakty i
twierdzenia z których korzystaliśmy przy budowie naszych modeli.
W razie wątpliwości co do znaczenia pewnych symboli używanych w tym i
następnych rozdziałach zachęcamy do korzystania z zestawienia wszystkich
oznaczeń znajdującego się w \hyperref[appendixA]{dodatku A}.

\section{Teoria Gier}

\label{zbiorGraczy}\label{zbiorStrategii}

Teoria Gier to jeden z najmłodszych działów matematyki.
Podstawowym pojęciem jest tu oczywiście \emph{gra}.
Niech $I$ będzie pewnym zbiorem graczy.
Dla każdego gracza $x \in I$ określamy zbiór jego możliwych strategii
$S_x$.
W trakcie rozgrywki gracz $x$ wybiera ze zbioru $S_x$ pewną strategię, którą
będzie się posługiwał.
Wybór strategii przez wszystkich graczy określamy mianem \emph{profilu}.

\begin{df}\label{profil}
\emph{Profil} $\bar{s}$ to krotka wybranych strategii indeksowana graczami,
$\bar{s}(x) \in S_x$ dla $x \in I$.
Zbiór wszystkich profili równy $\prod_{x \in I} S_x$ oznaczamy przez
$\overline{S}$.
\end{df}

\paragraph{}

W zależności od wybranej przez siebie strategii oraz strategii przeciwników
każdy gracz otrzymuje odpowiednią \emph{wypłatę}.
Wobec tego wypłatę gracza wygodnie jest zdefiniować jako funkcję ze zbioru
\emph{profili} w liczby rzeczywiste.

\begin{df}\label{wyplata}
\emph{Wypłatą} gracza $x \in I$ nazywamy funkcję
$u_x \, : \, \overline{S} \mapsto \mathbb{R}$.
\end{df}

\paragraph{}

W powyższych terminach formalna definicja gry przedstawia się następująco.

\begin{df}\label{gra}
\emph{Grą} $\mathcal{G}$ nazywamy trójkę uporządkowaną
$\big(I, \, (S_x)_{x \in I}, \, (u_x)_{x \in I}\big)$, gdzie\\
\begin{tabular}{ll}
$I$ & --- zbiór graczy,\\
$S_x$ & --- zbiór strategii gracza $x \in I$,\\
$u_x$ & --- wypłata gracza $x \in I$.\\
\end{tabular}
\end{df}

\paragraph{}

Szczególnym przypadkiem gry jest gra \emph{symetryczna}, to znaczy taka, w
której wszyscy gracze pełnią symetryczne role.

\begin{df}\label{graSymetryczna}
Grę $\big(I, (S_x)_{x \in I}, (u_x)_{x \in I} \big)$ nazywamy
\emph{symetryczną}, jeżeli każdy gracz dysponuje takim samym zbiorem możliwych
strategii, tzn.
\[ \forall x \in I \;\; S_x = S \]
oraz dla dowolnej permutacji $\tau \, : \, I \mapsto I$ graczy --- ich wypłaty
nie zmieniają się
\[
\forall \bar{s} \in \overline{S} \; \forall x \in I \;\; u_{\tau(x)}(\bar{s} \circ \tau^{-1}) = u_x(\bar{s})
\]
\end{df}

\paragraph{}\label{graSymDwuosobowa}\label{macierzWyplat}

My ograniczymy się do rozważań \emph{symetrycznych gier dwuosobowych.}
Bez straty ogólności możemy przyjąć, że $I = \{1, 2\}$.
Wówczas zbiór wszystkich możliwych profili to po prostu
$\overline{S} = S \times S$.
Natomiast warunek z definicji \ref{graSymetryczna}
uprości się do postaci:
\[ \forall s_a, s_b \in S \;\; u_1(s_a, s_b) = u_2(s_b, s_a) \]
\noindent
Zauważmy, że w przypadku gry symetrycznej wystarczy podać funkcję wypłaty tylko
dla jednego gracza, na przykład pierwszego.
W dalszym ciągu będziemy przyjmować, że $u$ jest wypłatą pierwszego gracza.
Jeśli założymy dodatkowo, że $S$ jest skończony i równy
$S = \{s_a, s_b, \dots\}$, to funkcję wypłaty będziemy mogli przedstawiać w
postaci tabeli:
\[
 \begin{array}{c|ccc}
   & s_a & s_b & \cdots \\
  \hline
  s_a & u(s_a,s_a) & u(s_a,s_b) \\
  s_b & u(s_b,s_a) & u(s_b,s_b) \\
  \vdots & & & \ddots
 \end{array}
\]
\noindent
Taką tabelę będziemy określać mianem \emph{macierzy wypłat}.

\subsection*{Dylemat Więźnia}\label{dylematWieznia}

\emph{Dylemat Więźnia} (patrz \ref{wstepDoDylematu})
jest przykładem symetrycznej gry dwuosobowej
(\ref{graSymDwuosobowa}).
Gracze mają do wyboru dwie strategie.
Mogą współpracować (ang. \emph{cooperate}) --- $C$ oraz zdradzać
(ang. \emph{defect}) --- $D$.
Jeśli jeden z graczy wybierze zdradę, a drugi będzie próbował naiwnie
współpracować, to ich wypłaty wyniosą odpowiednio
$u(D,C) = T$ (ang. \emph{temptation to defect}) oraz
$u(C,D) = S$ (ang. \emph{sucker's payoff}).
W przypadku gdy obaj gracze współpracują, to otrzymują wypłatę $u(C,C) = R$
(ang. \emph{reward}), a gdy obaj wybierają zdradę, to zarabiają po $u(D,D) = P$
(ang. \emph{punishment}).
Zakłada się, że zachodzą następujące nierówności:
\[
T > R > P > S, \;\;\; 2 \cdot R > T + S
\]
Wypłaty te można przedstawić w postaci macierzy wypłat.
\[
 \begin{array}{c|cc}
   & C & D\\
  \hline
  C & R & S\\
  D & T & P\\
 \end{array}
\]

\noindent
My będziemy rozważać dylemat więźnia w kanonicznej postaci:
\[
 \begin{array}{c|cc}
   & C & D\\
  \hline
  C & 3 & 0\\
  D & 5 & 1\\
 \end{array}
\]

\paragraph{}

Jednym z najważniejszych zagadnień w Teorii Gier jest pojęcie
równowagi zaproponowane przez słynnego amerykańskiego matematyka Johna Nasha.
Mówimy, że dany profil jest w \emph{równowadze Nasha}, jeśli zmiana strategii
dowolnego gracza nie powoduje zwiększenia jego wypłaty.

\begin{df}\label{rownowagaNasha}
Profil $\bar{s} \in \overline{S}$ jest w \emph{równowadze Nasha}, gdy spełnia
następujący warunek.
\[
\forall x \in I \; \forall s \in S_x \;\; u_x(\bar{s}[x \rightarrow s]) \leq u_x(\bar{s})
\]
\end{df}

\noindent
Racjonalni i chłodno kalkulujący gracze powinni wybierać strategie, które
podpowiada im równowaga Nasha.
Postępując w ten sposób uniezależnialiby swoje korzyści od wyborów przeciwników.

\section{Grafy}

Aspekty przestrzenne modelu będziemy wyrażali w języku teorii grafów.
Ze względu na rozbieżności w definicjach używanych przez różnych autorów,
pozwalamy sobie przytoczyć podstawowe pojęcia z tej dziedziny.
Dokładniejsze informacje można znaleźć w książce \cite{wdtg},
na której się wzorowaliśmy.

\medskip

\noindent
W matematyce wyróżnia się grafy \emph{nieskierowane} i \emph{skierowane}.
W naszej pracy rozważamy tylko skończone grafy nieskierowane, które będziemy
nazywać po prostu \emph{grafami} lub zamiennie \emph{sieciami}.

\subsection{Definicje}

\begin{df}\label{graf}
\emph{Skończonym grafem nieskierowanym (grafem, siecią)} nazywamy parę
$G = (V,E)$, gdzie
\begin{itemize}
\item[] $V \, = \, V(G)$ --- to zbiór wierzchołków grafu $G$,
\item[] $E \, = \, E(G)\subset \{\{v, w\} \; : \; v, w \in V \}$ --- to zbiór
        krawędzi grafu $G$.
\end{itemize}
\end{df}

\noindent
Zatem graf składa się z niepustego zbioru skończonego $V$, którego
elementy nazywamy \emph{wierzchołkami}, oraz skończonego zbioru $E$
nieuporządkowanych par elementów ze zbioru $V$ nazywanych \emph{krawędziami}.
Mówimy, że krawędź $\{v, w\}$ \emph{łączy} wierzchołki $v$ oraz $w$ i w tym
przypadku oznaczamy ją krócej symbolem $vw$.
Mówimy też wtedy, że wierzchołki $v$ i $w$ są \emph{incydentne} z tą krawędzią,
a je same nazywamy \emph{sąsiadami} w grafie $G$.
Podobnie dwie krawędzie $e$ i $f$ są \emph{sąsiednie}, jeśli mają wspólny
wierzchołek.
Czasem będziemy się interesować zbiorem wszystkich sąsiadów pewnego wierzchołka
$v$.
Pomocne okażą się nam następujące pojęcia.

\begin{df}\label{sasiedztwo}
Zbiór wszystkich sąsiadów wierzchołka $v$ w grafie $G$ nazywamy
\emph{sąsiedztwem} wierzchołka $v$ i oznaczamy przez $\mathcal{N}(v)$.
\end{df}

% \begin{df}\label{otoczenie}
% Przez \emph{otoczenie} wierzchołka $v$ rozumiemy zbiór składający się ze
% wszystkich sąsiadów wierzchołka $v$ i sam wierzchołek $v$, czyli
% $\mathcal{N}(v) \cup \{v\}$.
% Otoczenie oznaczamy przez $\overline{\mathcal{N}}(v)$.
% \end{df}
% DL: czy pojecie otoczenia jest nam potrzebne?
% LBK: Nie wiem jeszcze. Póki co wykomentuję.

\begin{df}\label{stopien}
Liczbę sąsiadów wierzchołka $v$ nazywamy jego \emph{stopniem} i oznaczamy przez
$deg(v) \; = \; |\mathcal{N}(v)|$.
\end{df}

\paragraph{}\label{grafProsty}\label{grafProsty}

\emph{Pętlą} nazywamy krawędź postaci $vv$.
Mówimy, że w grafie $G$ występują krawędzie wielokrotne, gdy pewne dwa
wierzchołki są połączone więcej niż jedną krawędzią.
W naszych rozważaniach ograniczymy się tylko i wyłącznie do grafów bez pętli i
krawędzi wielokrotnych.
Takie grafy są w literaturze nazywane \emph{grafami prostymi}.

\paragraph{}

Będziemy również potrzebować pojęcia \emph{trasy}.

\begin{df}\label{trasa}
\emph{Trasą} w danym grafie $G$ nazywamy skończony ciąg krawędzi postaci
$v_0v_1,v_1v_2,v_2v_3,\dots,v_{m-1}v_m$, w którym każde dwie kolejne krawędzie
są albo mają wspólny wierzchołek, albo są identyczne.
Taka trasa wyznacza ciąg wierzchołków $v_0, v_1, v_2, \dots, v_m$.
Liczbę krawędzi na trasie nazywamy jej \emph{długością}.
\end{df}

\paragraph{}\label{sciezka} \label{droga}\label{spojnosc} 

Trasę, w której wszystkie krawędzie są różne, nazywamy \emph{ścieżką}.
Jeśli dodatkowo wierzchołki $v_0, v_1, v_2, \dots, v_m$ są różne (być może z
wyjątkiem równości $v_0 = v_m$), to ścieżkę nazwiemy \emph{drogą}.
Powiemy, że graf $G$ jest \emph{spójny}, jeśli każde dwa wierzchołki są
połączone jakąś trasą.

\subsection{Charakterystyki}

Ten paragraf zawiera opis ważnych charakterystyk grafów.
W naszej pracy rozważamy modele konstruowane w oparciu o różne grafy, dlatego
potrzebujemy odpowiedniego języka, który pozwoli nam na określenie
cech odróżniających jedne grafy od drugich.

\paragraph{}
\label{liczbaWierzcholkow}\label{liczbaKrawedzi}\label{sredniStopien}

Najbardziej podstawowe charakterystyki to liczba wierzchołków $N = |V(G)|$ oraz
liczba krawędzi $M = |E(G)|$ w grafie.

% Bardzo przydatny okazuje się również \emph{średni stopień wierzchołka}
% oznaczany przez $\alpha$, czyli średnia liczba krawędzi wychodząca z jednego
% wierzchołka równa
% \[
% \alpha \; = \; \frac{1}{N} \sum_{v \in V} deg(v) \; = \; \frac{2 \cdot M}{N}
% \]
% DL: bardzo przydatny do czego?
% LBK: Dobra wywalę to póki co.

\paragraph{}\label{rozkladStopni}

Dużo informacji o strukturze grafu niesie ze sobą
\emph{rozkład stopni wierzchołków}.
Można go opisać za pomocą funkcji $\eta \, : \, \mathbb{N} \mapsto [0,1]$.
Przez $\eta(k)$ rozumiemy procentowy udział wierzchołków o stopniu $k$ w grafie.
\[
\eta(k) \; = \; \frac{N_k}{N} \; = \; \frac{|\{v \in V \, : \, deg(v) = k\}|}{N}
\]
Zauważmy, że ten sposób opisu rozkładu bardzo łatwo uogólnić na przypadek,
w którym stopnie to nie koniecznie liczby naturalne.

\paragraph{}\label{rozpietosc}

Inną charakterystyką jest \emph{rozpiętość} grafu, czyli średnia odległość
między wierzchołkami równa
\[
\frac{1}{N^2} \sum_{v,w \in V} dist(v,w)
\]
gdzie $dist(v,w)$ oznacza odległość wierzchołków $v$ i $w$ w grafie, czyli
długość najkrótszej łączącej je ścieżki.
Zwróćmy uwagę, że wartość ta jest poprawnie zdefiniowana jedynie dla grafów
spójnych.

\paragraph{}\label{klasteryzacja}

Kolejną ważną cechą jest średnia liczba połączeń pomiędzy sąsiadami jednego
wierzchołka.
Tę charakterystykę nazywamy \emph{klasteryzacją} i wyrażamy wzorem
\[
\frac{1}{N} \sum_{u \in V} \frac{2}{deg(u) \cdot (deg(u) - 1)} \sum_{\{v, w\} \in P(\mathcal{N}(u))} \big[\{v, w\} \in E\big]
\]

\paragraph{}

Wybraliśmy taki zestaw charakterystyk, gdyż ważną część naszej pracy stanowiły
badania sieci reprezentujących powiązania rodzinne i społeczne.
Takie grafy mają charakter sieci \emph{małego świata}.
Powszechnie uważa się, że rzeczywiste sieci społeczne, charakteryzują się dość
małą rozpiętością i wysokim współczynnikiem klasteryzacji.
Stanley Milgram postawił nawet słynną hipotezę o zaledwie ``sześciu stopniach
oddzielenia'', która była rezultatem przeprowadzonego przez niego eksperymentu
\emph{Small World} \cite{swp}.
Mówi ona, że każda para obywateli USA jest od siebie
oddalona drogą długości co najwyżej $6$ w sieci znajomości społecznych.

\subsection{Przykłady grafów}

\subsubsection*{Graf pełny}

W grafie pełnym wszystkie wierzchołki są połączone ze wszystkimi.
Jak ławo stwierdzić, w takim grafie zarówno rozpiętość jaki klasteryzacja są
równe $1$. Te liczby wskazują na to, że grafy pełne nie są zbyt ciekawymi
obiektami do analizy.

\subsubsection*{Pierścień $C_N$}

Pierścień $C_N$, to graf o $N$ wierzchołkach ($V = \{0,1,2,\dots,N-1\}$), które
można intuicyjnie przedstawiać jako umieszczone na okręgu.
Każdy węzeł ma dokładnie dwóch sąsiadów.
Sąsiadami wierzchołka o numerze $i$ dla $i \in \{0,\dots, N - 1\}$ są
wierzchołki $(i - 1) \mod N$ oraz $(i + 1) \mod N$.

\medskip

\noindent
Rozpiętość tego grafu jest rzędu $\frac{N}{4}$, a współczynnik klasteryzacji to
$0$.

\subsubsection*{Siatka z sąsiedztwem 4}

Siatka z sąsiedztwem 4 to graf, którego wierzchołki są umieszczone w punktach
kwadratowej kraty na płaszczyźnie, a dokładniej
$V = \{1, \dots, n\} \times \{1, \dots, m\} \subset \mathbb{N} \times \mathbb{N}$.
Krawędzie są wyznaczone przez geometryczne sąsiedztwo tych punktów, tzn.
każdy wierzchołek łączy się z czterema najbliższymi.
Przyjmujemy, że krata zawija się na brzegach, czyli np sąsiadem wierzchołka
$(m,i)$ jest wierzchołek $(1,i)$.
W ten sposób graf tak naprawdę można przedstawić jako umieszczony nie na
płaszczyźnie, a na torusie.

\begin{center}
\includegraphics[scale=0.5,viewport=130 600 260 730,clip]{siatki.pdf}
\end{center}

\medskip

\noindent
Rozpiętość tego grafu to około $\sqrt{N}$, a współczynnik klasteryzacji jest
równy $0$.
Siatka z sąsiedztwem 4 nie jest zatem siecią typu \emph{małego świata}.

\subsubsection*{Siatka z sąsiedztwem 6}

Siatka z sąsiedztwem 6 to graf, w którym stopień każdego wierzchołka wynosi 6.
Wierzchołki umieszczone są w punktach kratowych płaszczyzny, 
podobnie jak w przypadku siatki z sąsiedztwem 4
$V = \{1, \dots, n\} \times \{1, \dots, m\} \subset \mathbb{N} \times \mathbb{N}$.
Krawędzie łączą wierzchołki w czterech kierunkach kardynalnych: N, S, E, W, oraz
dwóch pobocznych: NE i SW. Tak samo jak w przypadku siatki z sąsiedztwem 4, 
aby uprościć warunki brzegowe, przyjmujemy, że krata zawija się na brzegach.

\begin{center}
\includegraphics[scale=0.5,viewport=130 450 260 580,clip]{siatki.pdf}
\end{center}

\medskip

\noindent
Rozpiętość tego grafu jest rzędu $\sqrt{N}$, a współczynnik klasteryzacji wynosi
$0,\!4$.

\subsubsection*{Siatka z sąsiedztwem 8}

Siatka z sąsiedztwem 8 jest bardzo podobna do siatki z sąsiedztwem 4.
Tu również wierzchołki są umieszczone w punktach kwadratowej kraty na
płaszczyźnie, a dokładniej
$V = \{1, \dots, n\} \times \{1, \dots, m\} \subset \mathbb{N} \times \mathbb{N}$.
Różnica polega tylko na wyznaczaniu połączeń --- w tym wypadku każdy
wierzchołek łączy się z ośmioma najbliższymi.
Podobnie jak poprzednio przyjmujemy, że krata zawija się na brzegach.

\begin{center}
\includegraphics[scale=0.5,viewport=130 300 260 430,clip]{siatki.pdf}
\end{center}

\medskip

\noindent
Ten graf charakteryzuje się średnią rozpiętością rzędu
$\sqrt{N}$ oraz dużym współczynnikiem klasteryzacji plasującym się na
poziomie $0,\!43$.

\section{Łańcuchy Markowa}

Łańcuchy Markowa są matematycznym narzędziem służącym do opisu stochastycznych
procesów zachodzących w czasie.
Zakładamy przy tym dyskretny bieg czasu.
Proces stochastyczny jest reprezentowany przez ciąg zmiennych losowych
indeksowanych kolejnymi liczbami naturalnymi.
Każda zmienna mówi w jakim stanie znajduje się proces w danym momencie.
Bardzo ważne jest \emph{założenie braku pamięci}, zgodnie z którym stan w jakim
znajdujemy się w momencie $(t + 1)$ może zależeć tylko od stanu, w którym
przebywaliśmy w chwili $t$.

\medskip

\noindent
Łańcuchy Markowa można definiować na wiele równoważnych sposobów.
My wzorujemy się na sposobie zaproponowanym przez prof. Stanisława Kwapienia
\footnote{prof. zwyczajny Stanisław Kwapień --- Zakład Teorii
Prawdopodobieństwa --- Instytut Matematyki --- Wydział Matematyki, Informatyki i
Mechaniki Uniwersytetu Warszawskiego}
podczas prowadzonych przez niego wykładów z \emph{Rachunku Prawdopodobieństwa}.

\begin{df}\label{lancuchMarkowa}
Ciąg zmiennych losowych $(X_t)_{t \in \mathbb{N}}$ o wartościach w przeliczalnej
przestrzeni stanów $Q$ nazywamy \emph{łańcuchem Markowa} gdy zachodzi
następująca własność dla dowolnych $t \in \mathbb{N}$ oraz
$q_0, q_1, q_2, \dots, q_t \in Q$:
\[
\mathbb{P}(X_t = q_t \, | \, X_{t-1} = q_{t-1}, \dots, X_1 = q_1, X_0 = q_0) = \mathbb{P}(X_t = q_t \, | \, X_{t-1} = q_{t-1})
\]
\end{df}

\noindent
Łańcuch Markowa możemy określić podając rozkład stanu początkowego $X_0$ oraz
prawdopodobieństwo przejścia między stanami.
Dla łańcuchów Markowa definiujemy następujące pojęcia.

\begin{df}\label{stanOsiagalny}
Mówimy, że stan $r$ jest \emph{osiągalny} ze stanu $q$, co oznaczamy
$q \rightarrow r$, gdy prawdopodobieństwo przejścia z $q$ do $r$ w skończonej
liczbie kroków jest dodatnie, tzn.
\[
\exists{n \in \mathbb{N}} \;\; \mathbb{P}(X_{t + n} = r \, | \, X_t = q) > 0
\]
\end{df}

\begin{df}\label{komnikacjaStanow}
Mówimy, że stany $q$ i $r$ się \emph{komunikują} gdy $q \rightarrow r$ oraz
$r \rightarrow q$.
\end{df}

\begin{df}\label{okresStanu}
Stan $q$ nazywamy \emph{okresowym} gdy istnieje dodatnia liczba naturalna $T$
(okres) taka, że prawdopodobieństwo przejścia ze stanu $q$ z powrotem do $q$
jest niezerowe tylko dla liczby kroków będących wielokrotnościami $T$.
Okres stanu $q$ oznaczamy przez.
\[
o(q) = nwd\{ k \in \mathbb{N} \; : \; \mathbb{P}(X_{t + k} = q \, | \, X_t = q) > 0\}
\]
Jeśli $o(q) = 1$, to mówimy, że stan $q$ jest \emph{nieokresowy}.
\end{df}

\begin{df}\label{lancuchNieprzykiedlny}
Łańcuch Markowa nazywamy \emph{nieprzywiedlnym}, jeśli każde jego dwa stany się
komunikują.
\end{df}

\begin{df}\label{lancuchNieokresowy}
Łańcuch Markowa nazywamy \emph{nieokresowym}, jeśli jego wszystkie stany są
nieokresowe.
\end{df}

\begin{df}\label{lancuchErgodyczny}
Łańcuch Markowa nazywamy \emph{ergodycznym}, jeśli jest nieprzywiedlny i
nieokresowy.
\end{df}

\paragraph{}

Zamiast mówić o konkretnym stanie łańcucha Markowa w danej chwili, możemy
rozważać cały rozkład możliwych stanów, czyli po prostu rozkład zmiennej losowej 
$X_t$.
Rozkład dla chwili $(t + 1)$ możemy łatwo wyznaczyć na podstawie
rozkładu dla chwili $t$ oraz prawdopodobieństw przejścia łańcucha.
Jest to pewien proces iteracyjny.
W takich sytuacjach często rozważa się zagadnienie punktu stałego
Rozkład będący punktem stałym łańcucha Markowa nazywamy rozkładem
\emph{stacjonarnym}.

Okazuje się, że ergodyczne łańcuchy Markowa zawsze posiadają
dokładnie jeden rozkład stacjonarny.
Fakt ten znany jest jako \emph{Twierdzenie Ergodyczne}.

\begin{tw}[Ergodyczne]\label{twErgodyczne}
Każdy ergodyczny łańcuch Markowa posiada dokładnie jeden
rozkład stacjonarny. Co więcej rozkład stanów łańcucha zbiega w czasie do
rozkładu stacjonarnego.
\end{tw}
